package com.yunsom.testdemo.leetcode.sort;

public class SortAlgorithmPractice {
    public static void main(String[] args) {
        int[] test1 = new int[]{1,5,3,6,8,2,10,6,0,4,7,2,9};
        System.out.println("排序前数组中元素为");
        for (int i : test1) {
            System.out.print(i + " ");
        }

        int[] test2 = fastSort(test1);
        System.out.println("\n" + "排序后数据元素为");
        for (int i : test2) {
            System.out.print(i + " ");
        }
    }

    /**
     * 冒泡排序
     * @param array
     * @return
     */
    public static int[] bubblingSort(int[] array){
        int temp;
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length -i - 1; j++) {
                if(array[j] > array[j+1]){
                    temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }
        return array;
    }

    /**
     * 选择排序
     * @param array
     * @return
     */
    public static int[] selectCompareSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            int min = array[i];
            int index = i;
            for (int j = i + 1; j < array.length; j++) {
                if(array[j] <= min){
                    min = array[j];
                    index = j;
                }
            }
            array[index] = array[i];
            array[i] = min;
        }

        return array;
    }

    /**
     * 快速排序-循环实现
     * @param array
     * @return
     */
    public static int[] fastSort(int[] array){
        quickSort(array, 0, array.length - 1);
        return array;
    }

    /**
     * 快速排序-循环实现
     * @param arr
     * @param start
     * @param end
     */
    public static void quickSort(int[] arr,int start,int end) {
        //基准下标的指示器
        int i;

        //区间存在两个及两个以上的元素,进行快排
        if(start<end)
        {
            //划分后基准的位置
            i = partition(arr, start, end);
            //左区间递归排序
            quickSort(arr, start, i-1);
            //右区间递归排序
            quickSort(arr, i+1, end);
        }
    }

    /**
     * 快速排序-循环实现:一趟划分,选取一个基准将无序区分为两部分,一部分比基准小,另一部分比基准大，等于基准的随意
     * @param arr
     * @param start
     * @param end
     * @return
     */
    public static int partition(int[] arr,int start,int end) {
        //设置两个指示器,指向头和尾
        int i=start,j=end;
        //选取基准，这里选取第一个元素做划分基准
        int temp = arr[i];

        //从两端向中间扫描,直至指示器 i=j 为止
        while(i<j) {
            //从右向左扫描,找到一个小于 temp 的 arr[j]
            while(j>i && arr[j]>=temp) {
                j--;
            }
            //找到这样的 arr[j],放到arr[i]处
            arr[i] = arr[j];

            //从左向右扫描,找到一个大于 temp 的 arr[i]
            while(i<j && arr[i]<=temp) {
                i++;
            }
            //找到这样的 arr[i],放到arr[j]处
            arr[j] = arr[i];
        }

        //划分完毕,基准回到正确位置
        arr[i] = temp;
        //返回此躺划分后的基准的下标
        return i;
    }

    /**
     * 快速排序-递归实现
     * @param arr
     * @param start
     * @param end
     */
    public static void quickSort1(int[] arr, int start, int end){
        int i;
        if(start < end){
            i = partition1(arr, start, end);
            quickSort1(arr, start, i-1);
            quickSort1(arr, i+1, end);
        }
    }

    /**
     * 快速排序-递归实现
     * @param arr
     * @param start
     * @param end
     * @return
     */
    public static int partition1(int[] arr, int start, int end){
        int i = start;
        int j = end;
        int temp = arr[i];

        while (i < j){
            while (j>i && arr[j] >= temp){
                j--;
            }
            arr[i] = arr[j];

            while (i<j && arr[i] <= temp){
                i++;
            }
            arr[j] = arr[i];
        }

        arr[i] = temp;
        return i;
    }

}
